package com.shu.Algorithm;

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayDeque;
import java.util.ArrayList;

/**
 * @author ssm
 * @version V1.0
 * @description:
 * @date 2020/9/4 11:28
 */

@Slf4j
public class SlideWindowSolution {


    public static void main(String[] args) {
        ArrayList<Integer> integers = SlideWindowSolution.maxInWindows(new int[]{1, 2, 3,7,1,5,0}, 2);
        System.out.println(integers);
    }


    public static ArrayList<Integer> maxInWindows(int[] num, int size) {
        ArrayList<Integer> res = new ArrayList<>();
        if (size == 0) return res;
        int begin;
        ArrayDeque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < num.length; i++) {
            begin = i - size + 1;
            if (q.isEmpty())
                q.add(i);
            else if (begin > q.peekFirst())
                q.pollFirst();

            while ((!q.isEmpty()) && num[q.peekLast()] <= num[i])
                q.pollLast();
            q.add(i);
            if (begin >= 0)
                res.add(num[q.peekFirst()]);
        }
        return res;
    }

}
